This paper gives a complete analysis of how many iterations are required for a Krylov subspace method to approximately solve the "trust region" and "cubic-regularized" quadratic minimization problems. These problems take the form: min x T A x b Tx subject to x R or with an additional regularization term of param* x 3. A is a symmetric, but not necessarily PSD matrix (i.e. it can have negative eigenvalues). The objective function is not necessarily convex. Problems of this form are important in a number of applications, especially as subroutines for regularized Newton methods. In addition to their practical importance, such methods have recently been used to give the fastest theoretical runtimes for finding stationary points and local minima of general non-convex objective functions.